package DFS;

import java.util.ArrayList;

/**
 * @Author: dust
 * @Date: 2019/11/18 16:27
 */
public class CC {

    private Graph G;
    private int[] visited;
    private int cccunt=0;

    public CC(Graph G) {

        this.G=G;
        visited=new int[G.V()];

        for(int i=0;i<visited.length;i++){
            visited[i]=-1;
        }

       for(int v=0;v<G.V();v++){
           if(visited[v]==-1){
               dfs(v,cccunt);
               cccunt++;
           }
       }
    }

    public int count(){
        return cccunt;
    }

    public boolean isConnected(int v,int w){
        G.validateVertex(v);
        G.validateVertex(w);
        return visited[v]==visited[w];
    }

    public ArrayList<Integer>[] components(){

        ArrayList<Integer>[] res=new ArrayList[cccunt];
        for(int i=0;i<cccunt;i++){
            res[i]=new ArrayList<>();
        }

        for(int v=0;v<G.V();v++){
            res[visited[v]].add(v);
        }

        return res;
    }

    private void dfs(int v,int ccid){
        visited[v]=ccid;
        for(int w:G.adj(v)){
            if(visited[w]==-1){
                dfs(w,ccid);
            }
        }

    }

    public static void main(String[] args) {
        Graph g=new Graph("g.txt");
        CC dfs=new CC(g);
        System.out.println(dfs.count());
    }

}
